package cn.zzf.algs.note.exercise.fundamental;

import edu.princeton.cs.algs4.StdOut;

import java.util.HashMap;

/**
 * @author GaoFeng
 * @date 2019/11/25 10:38
 */
public class Ex1_1_27 {

    private static HashMap<Integer, Double> resultMap = new HashMap<>();

    /**
     * 二项分布（Binomial Distribution），即重复n次的伯努利试验（Bernoulli Experiment），用ξ表示随机试验的结果。
     * 二项分布公式
     * 二项分布公式
     * 如果事件发生的概率是P,则不发生的概率q=1-p，N次独立重复试验中发生K次的概率是
     * P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k)，其中C(n, k) =n!/(k!(n-k)!)，注意：第二个等号后面的括号里的是上标，表示的是方幂。
     * 如果题目当中给出是“n次独立重复试验”这样的模型就需要用二项分布来解决了
     *
     * 符合以下4个特点的就是二项分布
     * 1、做某件事的次数是固定的；
     *
     * 2、每一次事件都有两个可能的结果（成功，或者失败）；
     *
     * 3、每一次成功的概率都是相等的；
     *
     * 4、你感兴趣的是成功x次的概率是多少。
     * 该递推公式来自: C(n,k)=C(n-1,k)+C(n-1,k-1)。实际场景是从n个人选k个，有多少种组合？
     * 将着n个人按1~n的顺序排好，假设第k个人没被选中，则需要从剩下的n-1个人中选k个；第k个选中了，则需要从剩下的n-1个人中选k-1个。
     * */
    public static double binomial(int n, int k, double p) {

        if (n == 0 && k == 0) {
            return 1.0;
        }

        if (n < 0 || k < 0) {
            return 0.0;
        }


        // TODO 暂时不会，预计使用记忆化搜索

        return (1.0 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
    }

    public static void main(String[] args) {
        double binomial = binomial(30, 5, 0.50);
        StdOut.println(binomial);
    }



}
